Contents of list

3.7 Linear Lists (list)

list E

1. Definition

An instance L of the parameterized data type is a sequence of items ( list $\_item$ ). Each item in L contains an element of data type E, called the element type of L. The number of items in L is called the length of L. If L has length zero it is called the empty list. In the sequel < x > is used to denote a list item containing the element x and L[i] is used to denote the contents of list item i in L.

2. Creation

creates an instance of type and initializes it to the empty list.

3. Operations

& truecm & truecm &

a) Access Operations

int length returns the length of L.

int size returns L.length().

bool empty returns true if L is empty, false otherwise.

list_item first returns the first item of L.

list_item last returns the last item of L.

list_item succ list_item it returns the successor item of item it, nil if it = L.last(). it is an item in L.

list_item pred list_item it returns the predecessor item of item it, nil if it = L.first(). it is an item in L.

list_item cyclic_succ list_item it returns the cyclic successor of item it, i.e., L.first() if it = L.last(), L.succ(it) otherwise.

list_item cyclic_pred list_item it returns the cyclic predecessor of item it, i.e, L.last() if it = L.first(), L.pred(it) otherwise.

list_item search E x returns the first item of L that contains x, nil if x is not an element of L

E contents list_item it returns the contents L[it] of item it it is an item in L.

E inf list_item it returns L.contents(it).

E head returns the first element of L, i.e. the contents of L.first(). L is not empty.

E tail returns the last element of L, i.e. the contents of L.last(). L is not empty.

int rank E x returns the rank of x in L, i.e. its first position in L as an integer from [1...| L|] (0 if x is not in L).

b) Update Operations

list_item insert E x, list_item it, direction dir=after inserts a new item < x > after (if dir = after) or before (if dir = before) item it into L and returns it. it is an item in L.

list_item push E x adds a new item < x > at the front of L and returns it ( L.insert(x, L.first(), before) )

list_item append E x appends a new item < x > to L and returns it ( L.insert(x, L.last(), after) )

E del_item list_item it deletes the item it from L and returns its contents L[it]. it is an item in L.

E pop deletes the first item from L and returns its contents. L is not empty.

E Pop deletes the last item from L and returns its contents. L is not empty.

void assign list_item it, E x makes x the contents of item it. it is an item in L.

void conc list& L1 appends list L1 to list L and makes L1 the empty list

void split list_item it, list& L1, L2 splits L at item it into lists L1 and L2 and makes L the empty list. More precisely, if L = x₁,..., x_k-1, it, x_k+1,..., x_n then L1 = x₁,..., x_k-1 and L2 = it, x_k+1,..., x_n it is an item in L.

void apply void (*f)(E&) for all items < x > in L function f is called with argument x (passed by reference).

void sort int (*cmp)(E&,E&) sorts the items of L using the ordering defined by the compare function cmp : E×E→int, < 0, if a < b with cmp(a, b) = 0, if a = b < 0, if a > b More precisely, if L = (x₁,..., x_n) before the sort then L = (x_π(1),..., x_π(n)) for some permutation π of [1..n] and cmp(L[x_j], L[x_j+1])≤ 0 for 1≤j < n after the sort.

void bucket_sort int i, int j, int (*f)(E&) sorts the items of L using bucket sort, where f : E→int with f (x)∈[i..j] for all elements x of L. The sort is stable, i.e., if f (x) = f (y) and < x > is before < y > in L then < x > is before < y > after the sort.

void permute the items of L are randomly permuted.

void clear makes L the empty list

c) Input and Output

void read istream I, char delim = '' reads a sequence of objects of type E terminated by the delimiter delim from the input stream I using the overloaded Read function (section 1.5) L is made a list of appropriate length and the sequence is stored in L.

void read char delim = '' Calls L.read(cin, delim) to read L from the standard input stream cin.

void read string s, char delim = '' As above, but uses string s as a prompt.

void print ostream O, char space = ' ' Prints the contents of list L to the output stream O using the overload Print function (cf. section 1.5) to print each element. The elements are separated by the character space.

void print char space = ' ' Calls L.print(cout, space) to print L on the standard output stream cout.

void print string s, char space = ' ' As above, but uses string s as a header.

d) Iterators

Each list L has a special item called the iterator of L. There are operations to read the current value or the contents of this iterator, to move it (setting it to its successor or predecessor) and to test whether the end (head or tail) of the list is reached. If the iterator contains a list $\_item$ ≠nil we call this item the position of the iterator. Iterators are used to implement iteration statements on lists.

void set_iterator list_item it assigns item it to the iterator it is in L or it = nil.

void init_iterator assigns nil to the iterator

list_item get_iterator returns the current value of the iterator

list_item move_iterator direction dir=forward moves the iterator to its successor (predecessor) if dir = forward (backward) and to the first (last) item if it is undefined (= nil), returns the iterator.

bool current_element E& x if the iterator is defined (≠ nil) its contents is assigned to x and true is returned else false is returned

bool next_element E& x L.move_iterator(forward) + return L.current_element(x)

bool prev_element E& x L.move_iterator(backward) + return L.current_element(x)

e) Operators

E& list_item it returns a reference to the contents of it.

listE& = L_1 The assignment operator makes L a copy of list L₁. More precisely if L₁ is the sequence of items x₁, x₂,...x_n then L is made a sequence of items y₁, y₂,...y_n with L[y_i] = L₁[x_i] for 1≤i≤n.

4. Iteration

forall_items(it, L) { ``the items of L are successively assigned to it'' }

forall(x, L) { ``the elements of L are successively assigned to x'' }

5. Implementation

The data type list is realized by doubly linked linear lists. All operations take constant time except for the following operations. Search and rank take linear time O(n), bucket_sort takes time O(n + j - i) and sort takes time O(n⋅c⋅log n) where c is the time complexity of the compare function. n is always the current length of the list.